package com.squirrel.michale;

import java.util.*;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/2 9:03 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class Exam_iLearning20221125 {



 

/**

 * OJ考题代码：目录树收缩

 *

 * @author 命题组

 * @since 2022-04-19

 */

 

class TreeNode {

    public String node;

    public TreeNode father;

    public List<TreeNode> child;

 

    public TreeNode(String node) {

        this.node = node;

        this.child = new ArrayList<>();

    }

}

class Solution {

    // 待实现函数，在此函数中填入答题代码;

    // 注：orgTree的每个元素为父子节点对，orgTree[i][0] = 父节点，orgTree[i][1] = 子节点

    int getNodesNum(String[][] orgTree, int depth) {

        Map<String,TreeNode> map = new HashMap<>();

        Set<String> childVal = new HashSet<>();

        for (String[] strings : orgTree) {

            TreeNode father = map.getOrDefault(strings[0], new TreeNode(strings[0]));

            TreeNode child = map.getOrDefault(strings[1], new TreeNode(strings[1]));

            father.child.add(child);

            map.put(strings[0], father);

            map.put(strings[1], child);

            childVal.add(strings[1]);

        }

        TreeNode root = new TreeNode("");

        for(String[] strings : orgTree) {

            if(childVal.add(strings[0])) {

                root = map.get(strings[0]);

                break;

            }

        }

 

        return getTargetNum(root,1,depth);

    }

 

    int getTargetNum(TreeNode node, int depth, int target){

        while (node.child.size()==1)

            node = node.child.get(0);

        if(depth==target)

            return 1;

        int result = 0;

        for(int i = 0; i < node.child.size(); i++) {

            result += getTargetNum(node.child.get(i),depth+1,target);

        }

        return result;

    }

 

    void dealInput(String[] strArr, int depth) {

        String[][] orgTree = Arrays.stream(strArr).map(el -> el.split(" "))

                .toArray(String[][]::new);

        int result = this.getNodesNum(orgTree, depth);

        System.out.println(result);

    }

}
}
